\documentclass[9pt,twocolumn]{article}          % LaTeX 2e
\usepackage{latex8}                              % LaTeX 2e
\usepackage{times}                               % LaTeX 2e

\usepackage{amsmath}
\usepackage[pdftex]{graphicx}
\usepackage{subfigure}

\begin{document}

\title{Papero Speculato}
\author{Christian Pilato \and Fabrizio Ferrandi \and Donatella Sciuto \\
\parbox{17cm}{\begin{center}
             Politecnico di Milano, Dip.\ di Elettronica e Informazione Milano, ITALY~~20133
             \end{center}}
}
%
\maketitle
\thispagestyle{empty}

\begin{abstract}
In this paper, we propose a novel methodology to address the register allocation problem in high-level synthesis. 
\end{abstract}

\section{Introduction}

High-Level Synthesis (HLS) of digital systems from a behavioral description has received significant
attention in the last 20 years.
%
The evolution of high-level design techniques has often been driven by
specific application domains, such as dataflow or arithmetic-intensive domain, which includes digital
signal and image processing, graphics, and several multimedia applications, and the control-flow or
decision-intensive application domain, which includes networking/telecommunication protocols, embedded
controllers, etc.
%
Data-dominated descriptions are characterized by a predominance
of arithmetic operations and the absence of control-flow constructs, while control-intensive ones
reflect a mix of arithmetic and logical operations, and control flow structures like loops
and conditional operations.
%
However, commercial synthesis tools have gained limited acceptance
among designers, primary due to poor synthesis results in present of conditionals and especially
loops, and lack of controllability of quality of results. In fact, for such designs, the control-flow
constructs often impose bottlenecks on the performance achievable using hardware and software implementations alike.

It has been shown that speculation is a promising technique for reducing such kind of performance
bottlenecks executing parts of a computation before the execution of the conditional operations that
decide whatever they need to be executed.

Lakshminarayana et al.~\cite{lakshminarayana97wavesched} proposed a scheduling algorithm targeted towards
minimizing the average execution time of control-flow intensive descriptions. They extended that approach~\cite{lakshminarayana00wavesched} incorporating also speculative execution.

\framebox{introduzione alla speculazione}

Lakshminarayana et al.~\cite{lakshminarayana00wavesched}

Kountouris and Wolinski~\cite{Kountouris2002}

Gupta et. al.~\cite{Gupta2001}

Cordone et al.~\cite{cordone2006aspdac}

\framebox{effetti della speculation sulla register allocation }

However, even if this technique is able far reduce the execution time of the specification, it needs to introduce in the architecture additional registers to store the more temporaries that are generated as well. This increases the design area that could overcome the global constraint. 

Herrmann and Ernst~\cite{herrmann97register}

In our opinion, this is a critical effect of speculation that has not been enough investigated in the past.


%
For these reasons, in this paper we address the overhead in term of registers introduced by speculative execution 
of control intensive designs. The main contributions of this work are: i) a formulation of liveness analysis that 
allows to avoid the compatibility/conflict graphs creations, ii) an algorithm for liveness analysis that is
able to fast compute temporaries alive across each cycle step boundary and their def/use chains; iii) a simple 
register binding heuristic that tries to minimize the interconnection elements.

This paper is organized as follows: in Section~\ref{sec:preliminaries} some important definition are given. 

\section{Preliminaries}\label{sec:preliminaries}

\section{Proposed Methodology}\label{sec:methodology}

\section{Experimental Results}\label{sec:results}

\section{Conclusion and Future Works}\label{sec:conclusion}


\bibliographystyle{latex8}
\bibliography{biblio}

\end{document}
